package com.frx.sort.quicksort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author ：frx
 * @date ：Created in 2019/10/27 19:37
 * @description：ToDO
 * @modified By：
 * @version: ToDO
 */
public class TestTwo {

    public static void main(String[] args){

        int[] arr = {8,5,7,6,2,1,3,0,4};
/*        int[] arr2 = {new Random(9).nextInt(),new Random(9).nextInt(),new Random(9).nextInt(),
                new Random(9).nextInt(),
                new Random(9).nextInt(),
                new Random(9).nextInt(),
                new Random(9).nextInt(),
                new Random(9).nextInt(),
                new Random(9).nextInt()};*/

        /*quickSort(arr2,0,arr.length-1);*/
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
        /*System.out.println(Arrays.toString(arr2));*/

    }
    public static void quickSort(int[] arr,int start,int end){
        if (start>= end){
            return;
        }
        int partition = partition(arr,start,end);
        quickSort(arr,start,partition-1);
        quickSort(arr,partition+1,end);
    }

    public static int partition(int[] arr,int start,int end){
        int pivot = start;
        int left = start;
        int right = end;
        while (left!=right){
            while (left<right && arr[left] < arr[pivot]){
                left++;
            }
            while (left<right && arr[right] > arr[pivot]){
                right--;
            }
            if (left <right){
                int tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
            }
        }
        int tmp = arr[pivot];
        arr[pivot] = arr[left];
        arr[left] = tmp;
        return left;
    }
}
